/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._101;

import javax.lang.model.element.VariableElement;
import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树，检查它是否是镜像对称的。
 *
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *
 *     1
 *    / \
 *   2   2
 *  / \ / \
 * 3  4 4  3
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 *
 *     1
 *    / \
 *   2   2
 *    \   \
 *    3    3
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._101
 * @ClassName: SymmetricTree
 * @Author: linyaonan
 * @Date: 2019/10/23 11:30
 */
public class SymmetricTree {

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        // 定义用来存放对应层节点数据的list
        List<ArrayList<Integer>> bufferList = new ArrayList<>();
        // 层数从0开始
        int index = 0;
        addList(root, index, bufferList);
        for (int i = bufferList.size() - 1; i >= 0; i--) {
            ArrayList<Integer> builder = bufferList.get(i);
            int count = builder.size() / 2;
            int max = builder.size() - 1;
            for (int i1 = 0; i1 < count; i1++) {
                Integer start = builder.get(i1);
                Integer end = builder.get(max - i1);
                if (start == null && end == null) {
                    continue;
                }
                if (start == null || end == null) {
                    return false;
                }
                // 判断数组是否为对称输出
                if (!builder.get(i1).equals(builder.get(max - i1))) {
                    return false;
                }
            }
        }
        return true;
    }


    private void addList(TreeNode node, int index, List<ArrayList<Integer>> bufferList) {
        appendData(node, index, bufferList);
        ++index;
        bufferData(index, bufferList, node.left);
        bufferData(index, bufferList, node.right);
    }

    private void bufferData(int index, List<ArrayList<Integer>> bufferList, TreeNode left) {
        if (left != null) {
            addList(left, index, bufferList);
        } else {
            appendData(null, index, bufferList);
        }
    }

    private void appendData(TreeNode node, int index, List<ArrayList<Integer>> bufferList) {
        if (bufferList.size() - 1 < index) {
            ArrayList<Integer> newBuilder = new ArrayList<Integer>();
            newBuilder.add(getNodeVal(node));
            bufferList.add(index, newBuilder);
        } else {
            ArrayList<Integer> builder = bufferList.get(index);
            builder.add(getNodeVal(node));
        }
    }

    private Integer getNodeVal(TreeNode node) {
        if (node == null) {
            return null;
        } else {
            return node.val;
        }
    }

}
